{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "24b2ce4a-deb1-453e-8b17-73f5a6190fb1",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/contains-duplicate-ii\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```cpp\n",
    "#include<bits/stdc++.h> \n",
    "\n",
    "using namespace std;\n",
    "\n",
    "template <typename T>\n",
    "std::vector<vector<T>> combinations(const std::vector<T>& v, std::size_t count)\n",
    "{\n",
    "    assert(count <= v.size());\n",
    "    std::vector<bool> bitset(v.size() - count, 0);\n",
    "    bitset.resize(v.size(), 1);\n",
    "\n",
    "    std::vector<vector<T>>  result;\n",
    "    do {\n",
    "        vector<T> subResult;\n",
    "        for (std::size_t i = 0; i != v.size(); ++i) {\n",
    "            if (bitset[i]) {\n",
    "                //std::cout << v[i] << \" \";\n",
    "                subResult.push_back(v[i]);\n",
    "            }\n",
    "        }\n",
    "        //std::cout << std::endl;\n",
    "        result.push_back(subResult);\n",
    "    } while (std::next_permutation(bitset.begin(), bitset.end()));\n",
    "\n",
    "    return result;\n",
    "}\n",
    "\n",
    "class Solution {\n",
    "public:\n",
    "    bool containsNearbyDuplicate(vector<int>& nums, int k) {\n",
    "        //8:17\n",
    "        map<int, vector<int>> num_dict;\n",
    "        for (int i=0; i<nums.size(); i++) {\n",
    "            int n = nums[i];\n",
    "            if (num_dict.find(n) == num_dict.end()) {\n",
    "                num_dict.insert(pair<int, vector<int>>(n, vector<int>{i}));\n",
    "            } else {\n",
    "                num_dict[n].push_back(i);\n",
    "            }\n",
    "        }\n",
    "        for (auto x : num_dict) {\n",
    "            if (x.second.size() >= 2) {\n",
    "                //cout << x.first << \":\" << x.second[0]<< \",\" << x.second[1] << endl;\n",
    "                for ( auto combination : combinations(x.second, 2)) {\n",
    "                    if (abs(combination[0] - combination[1]) <= k) {\n",
    "                        return true;\n",
    "                    }\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        return false;\n",
    "        //8:49\n",
    "        //debug until 8:54\n",
    "    }\n",
    "};\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}